import com.sun.deploy.util.LinkMouseListener;

import java.util.List;
//双向链表

public class MyLinkedList {
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head;
    public ListNode last;//为节点
    //展示
    public void display(){
        ListNode cur=head;
        while(cur!=null){
            System.out.println("cur.val="+cur.val+" ");
            cur=cur.next;
        }
    }
    //计算长度
    public int size(){
        ListNode cur=head;
        int count=0;
        while (cur!=null){
            cur=cur.next;
            count++;
        }
        return count;
    }
    //判断是否包含
    public boolean contains(int key){
        ListNode cur=head;
        while(cur!=null){
            if (cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //头插法
    public void addFirst(int data){
        ListNode node=new ListNode(data);
        if (head==null){
            head=node;
            last=node;
        }else{
            node.next=head;
            head.prev=node;
            head=node;
        }

    }
    //尾插法
    public void addLast(int data){
        ListNode node=new ListNode(data);
        //
        if (head==null){
            head=node;
            last=node;

        }else {
            last.next=node;
            node.prev=last;
            last=node;
        }
    }
    //指定位置插入
    public void addIndex(int index,int data){
        //检查index是否合法
        if(index<0||index>size()){
            return ;
        }
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNode node=new ListNode(data);
        ListNode cur=findIndex(index);
        //先改后继
        node.next=cur;
        cur.prev.next=node;
        //改前驱
        node.prev=cur.prev;
        cur.prev=node;

    }
    //找到指定位置
    public ListNode findIndex(int index){
        ListNode cur=head;
        while(index!=0){//cur从head开始走index次，走完后下标为原来的index
            cur=cur.next;
            index--;
        }
        return cur;
    }
    //删除val=key的节点
    public void remove(int key){
        ListNode cur=head;
        while(cur!=null){
            //开始删除
            if(cur.val==key){
                if (cur==head){//如果要删的节点为头节点
                    head=head.next;
                    if(head!=null){//如果不是只有一个节点
                        head.prev=null;
                    }

                }else{//中间  //尾巴的情况
                    if(cur.next!=null){//中间
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }else {//尾巴
                        cur.prev.next=cur.next;//此时cur.next为null
                        last=last.prev;
                    }
                }
                return;
            }
            cur=cur.next;//不进入if语句就往后走
        }

    }
    //删除所有key值的节点
    public void removeAllKey(int key){
        ListNode cur=head;
        while(cur!=null){
            //开始删除
            if(cur.val==key){
                if (cur==head){//如果要删的节点为头节点
                    head=head.next;
                    if(head!=null){//如果不是只有一个节点
                        head.prev=null;
                    }

                }else{//中间  //尾巴的情况
                    if(cur.next!=null){//中间
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }else {//尾巴
                        cur.prev.next=cur.next;//此时cur.next为null
                        last=last.prev;
                    }
                }
                //这里删除return;
            }
            cur=cur.next;//不进入if语句就往后走
        }
    }
    //清空链表
    public void clear() {
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur=curNext;
        }
        head = null;
        last = null;
    }
}
